区间dp 置顶 | 发布于 2020-07-11 | 分类于 dp 、 区间dp | 19分钟 | 3285字数 一.概念 对于一段区间求最优解,且该区间可以分为几个小区间的最优解合并(最优子结构)。 二.基本思路 阅读全文 »
伯努利数 置顶 | 发布于 2020-07-11 | 分类于 数学 、 伯努利数 | 8分钟 | 1346字数 伯努利数是一个用于解决 nnn 次方和的数列。 它的递归定义公式如下: ∑i=0n(n+1i)Bi=[n=0] (1.1)\sum_{i=0}^n \binom {n+1} i B_i=[n=0] ~~~~~~~~ (1.1) 阅读全文 »
数论函数综合 置顶 | 发布于 2020-07-05 | 分类于 数论 、 莫比乌斯反演 | 22分钟 | 3887字数 一.数论函数 1.定义 数论函数是 : 其定义域是正整数,值域是一个数集的函数。 阅读全文 »
2020.11.20 模拟赛 发布于 2020-11-25 | 分类于 模拟赛 、 线段树 、 数论 、 图论 | 8分钟 | 1513字数 T1\text{T1} T1 Subtask 1 40 pts 阅读全文 »
CF575A Fibonotci 发布于 2020-11-25 | 分类于 矩阵乘法 、 线段树 | 1分钟 | 164字数 考试的时候写了3.5h , 考后又写了2h 才过掉。 每次修改只会影响两个矩阵,可以暴力计算。 我们知道矩阵乘法有结合律,那么两次修改之间的矩阵可以快速求出乘积。 阅读全文 »
P5437 【XR-2】约定 发布于 2020-11-25 | 分类于 拉格朗日插值 | 6分钟 | 889字数 每一条边被选中的概率: n−1n(n−1)2=2n\frac{n-1}{\frac{n(n-1)}{2}}=\frac{2}{n}2n(n−1)n−1=n2 所以答案为: 2n∑i=1n−1∑j=i+1n(i+j)k\frac{2}{n} \sum_{i=1}^{n-1} \sum_{j=i+1}^n (i+j)^k 阅读全文 »
P5929 [POI1999]地图 发布于 2020-11-25 | 分类于 dp | 3分钟 | 480字数 至少有一半不小于 A(k)A(k)A(k) , 至少有一半不大于 A(k)A(k)A(k) 所以 A(k)A(k)A(k) 应该是选出的区域人口的中位数。 为了使误差尽可能小,每次应该取排序后连续的一段区间染相同颜色。 阅读全文 »
CF757E Bash Plays with Functions 发布于 2020-11-25 | 分类于 数论 | 4分钟 | 635字数 根据题意进行分类讨论: 令 τ(n)\tau(n)τ(n) 为 nnn 的不同质因数的个数。 阅读全文 »
SP4060 KPGAME - A game with probability 发布于 2020-11-25 | 分类于 博弈论 、 概率dp | 5分钟 | 720字数 dp[0/1][i]dp[0/1][i]dp[0/1][i] :有 iii 颗石子 Alice/Bob 为先手,Alice 赢的概率 令 PPP 为 Alice 拿走石子的概率, QQQ 为 Bob 拿走石子的概率。 {dp[0][i]=dp[1][i−1]∗P+dp[1][i]∗(1−P)dp[1][i]=dp[0][i−1]∗Q+dp[0][i]∗(1−Q)\begin{cases} 阅读全文 »